package com.company;

import org.jetbrains.annotations.NotNull;

import java.util.Arrays;

// 给定一个含有 n 个正整数的数组和一个正整数 s
// 找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。
// 如果不存在符合条件的连续子数组，返回 0。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public class MinSubArrayLen {
    public int min(int s, @NotNull int[] nums) {
        int max = nums.length;
        int min = 0;
        while (min <= max) {
            int mid = (max + min) / 2;
            int sum = this.sum(nums, mid);
            if (sum >= s) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        return min > nums.length ? 0 : min;
    }

    public int sum(@NotNull int[] nums, int len) {
        int total = 0;
        int s = 0;
        for (int i = 0; i < len; i++) {
            total += nums[i];
            s = total;
        }
        for (int i = len; i < nums.length; i++) {
            total += nums[i] - nums[i -len];
            s = Math.max(s, total);
        }
        return s;
    }

    public static void main(String[] args) {
        MinSubArrayLen len = new MinSubArrayLen();
        System.out.println(len.min(7, new int[]{2, 3, 1, 2, 4, 3})); // 2
    }
}
